/*
 * Copyright (c) 2018. Lorem ipsum dolor sit amet, consectetur adipiscing elit.
 * Morbi non lorem porttitor neque feugiat blandit. Ut vitae ipsum eget quam lacinia accumsan.
 * Etiam sed turpis ac ipsum condimentum fringilla. Maecenas magna.
 * Proin dapibus sapien vel ante. Aliquam erat volutpat. Pellentesque sagittis ligula eget metus.
 * Vestibulum commodo. Ut rhoncus gravida arcu.
 */

package com.j4dream.property.leetcode.basic;

import java.util.*;

public class ArrayBasic {

    public int removeDuplicates(int[] nums) {
        int currIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[currIndex] != nums[i]) {
                nums[++currIndex] = nums[i];
            }
        }
        return ++currIndex;
    }

    public int maxProfit(int[] prices) {
        return 0;
    }

    public void moveZeroes(int[] nums) {
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[index++] = nums[i];
            }
        }
        for (int j = index; j < nums.length; j++) {
            nums[j] = 0;
        }
    }

    //    给定一个非负整数组成的非空数组，在该数的基础上加一，返回一个新的数组。
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] res = new int[2];
        for(int i= 0; i< nums.length; i++){
            int find = target - nums[i];

            if (map.containsKey(find)) {
                res[0] = map.get(find);
                res[1] = i;
                return res;
            }
            map.put(nums[i], i);
        }
        return res;
    }


    // 三数之和: 三层循环 判断 a+b+c=0, 去重, 但速度太慢.
    public List<List<Integer>> threeSum(int[] nums) {
        if (nums == null) return null;
        if (nums.length < 3) return new ArrayList<>();
        Arrays.sort(nums);

        HashSet<List<Integer>> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            int j = i+1;
            int k = nums.length - 1;
            // 可以局部再优化一下: 三个数中一定有一个负数.
            while (j < k) {
                if (nums[i] + nums[j]+nums[k]==0) {
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[k]);
                    set.add(list);
                    while (j < k && nums[j] == nums[j+1]) {
                        j++;
                    }
                    while (j < k && nums[k] == nums[k -1]) {
                        k--;
                    }
                    j++;
                    k--;
                } else if (nums[i] + nums[j]+nums[k]<0) {
                    j ++;
                } else {
                    k--;
                }
            }
        }
        return new ArrayList(set);
    }

//    给定一个非负整数组成的非空数组，在该数的基础上加一，返回一个新的数组。
//    最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。
//    你可以假设除了整数 0 之外，这个整数不会以零开头。
    public int[] onePlus(int[] digits) {
        boolean flag = false;
        int i = digits.length - 1;
        digits[digits.length - 1] += 1;
        while (i >= 0) {
            if (flag) {
                digits[i] += 1;
            }
            if (digits[i] == 10) {
                flag = true;
                digits[i] = 0;
            } else {
                flag = false;
            }
            i--;
        }

        if (flag) {
            int[] res = new int[digits.length + 1];
            res[0] = 1;
            return res;

        }
        return digits;
    }


    public boolean isValidSudoku(char[][] board) {
        boolean isValid = true;

        HashSet<Character> rowSet = new HashSet<>();
        HashSet<Character> colSet = new HashSet<>();
        HashSet<Character> smallSet = new HashSet<>();

        for (int r = 0; r < board[0].length; r++) {
            for (int c = 0; c < board.length; c++) {
                if ('.' != board[r][c]) {
                    if (!rowSet.add(board[r][c])) return false;
                }

                if ('.' != board[c][r]) {
                    if (!colSet.add(board[c][r])) return false;
                }
                if (r % 3 != 0) {
                    smallSet.clear();
                    continue;
                }
                if (c % 3 == 0) {
                    smallSet.clear();
                }
                if ('.' != board[r][c] && !smallSet.add(board[r][c])) return false;
                if ('.' != board[r + 1][c] && !smallSet.add(board[r + 1][c])) return false;
                if ('.' != board[r + 2][c] && !smallSet.add(board[r + 2][c])) return false;
            }
            rowSet.clear();
            colSet.clear();
        }

        return isValid;
    }

    // 矩阵向右旋转90度
    public void rotate(int[][] matrix) {
        int R = matrix.length, C = matrix[0].length;
        // 开辟新空间，不符合原要求。
//        int[][] res = new int[R][C];

//        for(int r = 0; r < R; r++) {
//            for(int c = 0; c < C; c++) {
//                //int temp = matrix[c][C - r];
//                res[c][C - 1 - r] = matrix[r][c];
//            }
//        }
//
//        for (int i = 0; i < R; i++) {
//            for (int j = 0; j < R; j++) {
//                matrix[i][j] = res[i][j];
//            }
//        }

        // 先对角线对换
        for (int r = 0; r < R; r++) {
            for (int c = r; c < C; c++) {
                int temp = matrix[r][c];
                matrix[r][c] = matrix[c][r];
                matrix[c][r] = temp;
            }
        }

        // 再交互列
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C / 2; c++) {
                int temp = matrix[r][c];
                matrix[r][c] = matrix[r][R - 1 - c];
                matrix[r][R - 1 - c] = temp;
            }
        }

        System.out.println(matrix);
    }


}
